"""
题目：源点是指有向图中 “没有入边，只有出边” 的顶点，给定一个有向图，判断指定顶点是否为源点。
"""


class Graph:
    def __init__(self, is_directed=False):
        self.vertices = {}
        self.is_directed = is_directed

    def add_vertex(self, vertex):
        if vertex not in self.vertices:
            self.vertices[vertex] = []

    def add_edge(self, v1, v2):
        self.add_vertex(v1)
        self.add_vertex(v2)
        self.vertices[v1].append(v2)
        if not self.is_directed:
            self.vertices[v2].append(v1)

    def is_source_vertex(self, vertex):
        """判断有向图中指定顶点是否为源点（无入边，有出边）"""
        # 非有向图或顶点不存在，直接返回False
        if not self.is_directed or vertex not in self.vertices:
            return False

        # 条件1：有出边（邻接列表非空）
        has_out_edge = len(self.vertices[vertex]) > 0
        # 条件2：无入边（其他所有顶点的邻接列表中不含该顶点）
        has_in_edge = False
        for v in self.vertices:
            if v == vertex:
                continue  # 跳过自身
            if vertex in self.vertices[v]:
                has_in_edge = True
                break

        return has_out_edge and not has_in_edge


# 测试
if __name__ == "__main__":
    dir_graph = Graph(is_directed=True)
    dir_graph.add_edge('A', 'B')
    dir_graph.add_edge('A', 'C')
    dir_graph.add_edge('B', 'D')
    dir_graph.add_edge('C', 'D')

    print(dir_graph.is_source_vertex('A'))  # 输出: True（无入边，有出边A→B、A→C）
    print(dir_graph.is_source_vertex('B'))  # 输出: False（有入边A→B）
    print(dir_graph.is_source_vertex('D'))  # 输出: False（无出边）